package algorithms.sort;

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        int[] arr = GetRandomArr.getRandomArr(3);
        System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        //bubbleSort(arr);
        bubbleSortImprove(arr);
        long end = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println("耗时："+(end-start)+"ms");
    }

    /**
     * 冒泡排序
     * 时间复杂度O(n^2)
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        if(arr == null || arr.length <=1)
            return;
        for (int i=0;i<arr.length-1;i++) {// n个数据，就要进行n-1次比较
            for (int j = 0; j < arr.length-i-1; j++) {// 第i次，要进行n-i-1次比较
                if(arr[j] > arr[j+1]){
                    swap(arr, j, j+1);
                }
            }
        }
    }

    /**
     * 冒泡排序（改进版）
     * 时间复杂度O(n^2)
     * 最好情况O(n)
     * @param arr
     */
    public static void bubbleSortImprove(int[] arr){
        if(arr == null || arr.length <=1)
            return;
        int j = arr.length -1;// 需要比较次数
        boolean flag = true;// 是否需要交换标志位
        while (flag) {
             flag = false;// 每次置为false
            for(int i = 0;i < j;i++) {
                if (arr[i] > arr[i+1]) {
                    swap(arr,i,i+1);
                    flag = true;// 需要交换
                }
            }
            j--;
        }
    }

    private static void swap(int[] arr, int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static int binarySearch(int[] arr,int val){
        int maxIndex = arr.length-1;
        int minIndex = 0;
        while (minIndex<=maxIndex){
            int midIndex = (maxIndex + minIndex) / 2;
            int aimVal = arr[midIndex];
            if(aimVal<val){// 大于找右边
                minIndex = midIndex +1;
            }
            if(aimVal>val){// 小于找左边
                maxIndex = midIndex -1;
            }
            if(aimVal==val){// 相等返回下标
               return midIndex;
            }
        }
        // 没有找到
        return -(minIndex+1);
    }


    public static void insertSort(int[] arr){
        for (int i=0;i<arr.length-1;i++){
            int minIndex =i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<arr[minIndex]){
                    minIndex=j;
                }
            }
            int temp = arr[i];
            arr[i]=arr[minIndex];
            arr[minIndex]=temp;
        }
    }




}
